package com.dsaa.dp;

class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "cbbd";
        System.out.println("input  :" + s);
        String res = solution.longestPalindrome(s);
        System.out.println("output :" + res);
    }

    public String longestPalindrome(String s) {
        String ans = "";
        for (int i = 0; i < s.length(); i++) {
            //长度为奇数，i 为中心点，向两边查找相同的回文串
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                l--;
                r++;
            }
            if (ans.length() < r - l - 1) {
                ans = s.substring(l + 1, r);
            }

            //长度为偶数，i 为中心点，向两边查找相同的回文串
            l = i;
            r = i + 1;
            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                l--;
                r++;
            }
            if (ans.length() < r - l - 1) {
                ans = s.substring(l + 1, r);
            }
        }
        return ans;
    }
}